package com.fufu.algorithem.sort;

import java.util.Arrays;

/**
 * @author: BlcakTiger
 * @date: 2023/2/25 9:00
 * @contact: hsf6661@163.com
 */
public class Quick {

    public static void main(String[] args) {
        //初始化数组
        int[] arr = new int[80000];
        //随机赋值
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 1000000);
        }
        //记录执行排序前的时间
        long ori = System.currentTimeMillis();
        //排序
        sort(arr, 0, arr.length - 1);
        //记录排序后的时间
        long cur = System.currentTimeMillis();
        //计算时间
        System.out.println((cur - ori) * 1.0 / 1000);
//        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr, int left, int right) {
        //基准点
        int pivot = arr[(left + right) / 2];
        //左指针
        int l = left;
        //右指针
        int r = right;

        //循环遍历基准两边的数
        while (true) {
            //查找大于等于基准的数，若当前元素小于基准，移动左指针
            while (arr[l] < pivot) {
                l += 1;
            }

            //查找小于等于基准的数，若当前元素大于基准，移动右指针
            while (arr[r] > pivot) {
                r -= 1;
            }
            //当左指针大于等于右指针时，说明基准左边已经都是小于基准的数，基准的右边都是大于基准的数
            //这时候就可以直接结束循环了
            if (l == r) {
                break;
            }
            //交换左右两边的元素
            arr[l] = arr[l] ^ arr[r];
            arr[r] = arr[l] ^ arr[r];
            arr[l] = arr[l] ^ arr[r];
            //当l指向的元素==pivot时，需要将r

        }

        if (l == r) {
            l++;
            r--;
        }
        if (left < r) {
            sort(arr, left, r);
        }
        if (right > l) {
            sort(arr, l, right);
        }

    }
}
